НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №1 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «РЕКУРСИВНІ АЛГОРИТМИ» Варіант № 16 Дата «15» квітня 2022  Київ 2022 Мета роботи: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціями. Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму. Завдання: / рис 1. Теоретичні відомості: Алгоритм – це скінченна послідовність команд, які треба виконати над вхідними даними для отримання результату. Основними мірами обчислювальною складності алгоритмів є: – часова складність, яка характеризує час, необхідний для виконання алгоритму на даній машині; цей час, як правило, визначається кількістю операцій, які потрібно виконати для реалізації алгоритму; – ємнісна складність, яка характеризує пам’ять, необхідну для виконання алгоритму. Часова та ємнісна складність тісно пов’язані між собою. Обидві є функціями від розміру вхідних даних. Надалі обмежимося тільки аналізом часової складності. Складність алгоритму описується функцією f(n), де n – розмір вхідних даних. Важливе теоретичне і практичне значення має класифікація алгоритмів, яка бере до увагу швидкість зростання цієї функції. Асимптотична складність алгоритму - спосіб оцінки обчислювальної складності алгоритму «з точністю до константи», застосовуваний в теорії складності. Зазвичай записується в нотації «великого О». Поширені складності алгоритмів Складність Коментар Приклади  O(1) Сталий час роботи не залежно від розміру задачі Очікуваний час пошуку в хеші  O(log n) Логарифмічне зростання — подвоєння розміру задачі збільшує час роботи на сталу величину Обчислення xn; двійковий пошук в масиві з n елементів  O(n) Лінійне зростання — подвоєння розміру задачі подвоїть і необхідний час Додавання/віднімання чисел з n цифр; лінійний пошук в масиві з n елементів  O(n²) Квадратичне зростання — подвоєння розміру задачі вчетверо збільшує необхідний час Елементарні алгоритми сортування   Хід роботи: Написано програмний код, що створює двовимірнинй динамічний масив випадко вих цілих чисел розмір якого задається через консоль. В результаті програма просить ввід кількості елементів масиву, виводить початковий масив та масив після 1 та 2 завдання. Для завдання 1 програма шукає в рядку максимальний елемент, а потім перезаписує значення елемента на побічній діагоналі на найменше. Для завдання виконав перевірку, якщо мінімальний елемент є першим елементом, то масив не виводиться, а виводиться повідомлення. Було проведено оцінку часової складності алгоритму та порівняно час роботи та кількість ітерацій з різною розмірністю масиву (10x10, 50x50, 100x100, 500x500). Оцінку часу роботи наведено нижче у вигляді таблиці та графіку. Було створенно декілька методів для полегшення метода main, тому для першого завдання було викростано 4 методу: для оголошення массиву, його перетворення та два виводу. У getMatrix ми маємо цикл в циклі. Перший раз for(int i=0; i<size;i++) ми виконуемо 3 ітерації: ініціалізація і, перевірка, та прирост і. Далі у циклу виконується size-1 раз вже по дві ітерації: перевірка і прирост, і останній раз одна ітерація – перевірка, тому можна звести до формули 3+2*n+1=4+2n. Далі вкладений цикл такий самий і потім вже у ньому лінійні дії які можна звести до (4+2n+3)*n. Тому увесь цей метод можна спростити до 2n^2+9n+4 = Θ(n^2). У методі perevertMatrix ми спочатку знаходимо найменший член матриці, а потім зміна рядка на стовпчик і навпаки, згідно знаходження знайденого члена. Аналогічно метод можна звести до формули 4+2n + (4+2n)n + 3n^2(для if беремо найгірший варіант, тобто коли він виконується кожний раз у циклі – n^2) + (4+2n) + 3n(перестановка елементів) = 5n^2+11n+8 = Θ(n^2). Метод ...